package demo2;

import java.util.Iterator;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-27
 * Time: 19:23
 */
public class BinarySearchTree {

    static class TreeNode{
        public int val;
        public TreeNode left ;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;

    public boolean insert(int key){
        if(root==null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        TreeNode node= new TreeNode(key);;
        while(cur!=null){
            if(cur.val>key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val<key){
                parent = cur;
                cur = cur.right;
            }else {
                return false;
            }
        }
        //此时cur为空节点 cur有可能比parent大也有可能比parent小
        if(parent.val>key){
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;

    }

    public TreeNode search(int key){
        if(root==null) return null;
        TreeNode cur = root;
        while(cur!=null){
            if(cur.val>key){
                cur = cur.left;
            }else if(cur.val<key){
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }

    public void remove(int key){
        if(root==null) return ;
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur!=null){
            if(cur.val>key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val<key){
                parent = cur;
                cur = cur.right;
            }else {
                //已经找到key了需要删除这个节点
                removeNode(cur,parent);
                return;
            }
        }
    }

    public void removeNode(TreeNode cur,TreeNode parent){
         if(cur.left==null){
             if(root==cur){
                 root = root.right;
             }else if(cur==parent.right){
                 parent.right = cur.right;
             }else {
                 parent.left = cur.right;
             }
         }else if(cur.right==null) {
             if(root==cur){
                 root = root.left;
             }else if(cur == parent.left){
                 parent.left = cur.left;
             }else {
                 parent.right = cur.left;
             }
         }else {
             //两者都不为空的时候要采用替换法
             //可以在右树中找最小值替换，也可以在左树中找最大值替换
             //这里选择在左树中找最大值替换
             TreeNode targetParent = cur;
             TreeNode target = cur.left;
             while(target.right!=null){
                 targetParent=target;
                 target = target.right;
             }
             cur.val = target.val;
             //删除target
             if(targetParent.right==target){
                 targetParent.right = target.left;
             }else {
                 targetParent.left = target.left;
             }
//             TreeNode targetParent = cur;
//             TreeNode target = cur.right;
//             while(target.left!=null){
//                 targetParent=target;
//                 target = target.left;
//             }
//             cur.val = target.val;
//             //删除target
//             if(targetParent.left==target){
//                 targetParent.left = target.right;
//             }else {
//                 targetParent.right = target.right;
//             }
         }


    }


}
